Linear computational cost graph grammar based direct solver for 3D adaptive finite element method simulations

摘要

In this paper we present a new graph grammar based direct solver algorithm delivering linear O(N) computational cost and linear O(N) memory usage for adaptive finite element method simulations. Classical direct solvers on regular grids deliver O(N1.5) complexity for 2D problems and O(N2) in 3D ones. The linear computational cost of our solver is obtained by generating graph representation of the adaptive mesh and by utilizing dynamic construction prescribing the solver algorithm as graph grammar productions.